In general, in communication systems using an error correction encoding method and device, the larger the code rate, the higher becomes the efficiency of communication, but the lower becomes error correction capability. On the contrary, the lower the code rate, the lower becomes the efficiency of communication, but the higher becomes error correction capability. As a result, it becomes important to set the code rate in an appropriate manner according to the status of communication channels. Here, note that the code rate is a value “k/n” (=1−(the number of lines/the number of rows)) which is represented by the use of a code length n and an information sequence length k of an error correcting code.
In view of the above-mentioned technical background, in the past, in some communication systems, a plurality of error correcting codes of different encoding rates are installed or implemented on a communication system, so that a change-over setting of the coding rates can be made according to the status of the communication channels, etc.
In addition, low-density parity-check codes (Low-Density Parity-Check codes: hereinafter referred to as an “LDPC codes”) are known as one scheme from the past.
The LDPC codes are codes which are defined by a parity check matrix in which elements of “1” are sparse (they exist at small proportion with respect to the number of all elements), and a row number n of the parity check matrix serves as a code length, and a column number m corresponds to a check bit (parity bit) number.
The number of “1s” which are contained in a column of the parity check matrix is referred to as a “column weight” in that column, and a distribution of the values of the column weights of individual columns is referred to as a “column weight distribution”.
Although the column weight distribution influences the error correction capability of an LDPC code to a large extent, an optimal column weight distribution can be calculated from a density evolution method, etc.
In addition, similarly, the number of “1s” which are contained in a row of the parity check matrix is referred to as a “row weight” in that row.
Moreover, the parity check matrix can be expressed by a bipartite graph which is called a Tanner graph, but the larger the length of the shortest loop contained in the Tanner graph, the more the error floor of the LDPC code is reduced.
In the LDPC code, as the encoding rates thereof are different, the parity check matrices thereof also become different, and calculation operations carried out for encoding and decoding are dependent on the parity check matrices.
Accordingly, in cases where LDPC codes with a plurality of encoding rates are implemented on a single communication system, it becomes necessary to prepare a different encoder and decoder for each encoding rate.
For this reason, in the past, there have been developed Rate-Compatible LDPC codes (hereinafter referred to as “RC-LDPC codes”) which serve to construct a communication system in an efficient manner by sharing circuits among a plurality of LDPC codes of different encoding rates.
In the design of RC-LDPC codes, a parity check matrix of an LDPC code with a high encoding rate is constructed in many cases, so that it matches a sub-matrix of a parity check matrix thereof with a low encoding rate, but it is difficult to provide optimal column weight distributions on both of the two kinds of encoding rates.
Accordingly, there has been proposed a technique in which a parity check matrix with a low encoding rate is first prepared, and the number of rows thereof is then increased by dividing a part of the rows into two rows, and at the same time, some columns are added, so that it is made possible to change over between two kinds of different encoding rates, for a parity check matrix before the row division and a parity check matrix after the row division (for example, see a first patent document).
In the conventional technique described in the above-mentioned first patent document, by devising the columns to be added, a structure of a staircase or step matrix (to be described later) is given to a parity check matrix, so that the construction of an encoding operation can be made to be adapted to or compatible with a change-over among the variable encoding rates in an efficient manner.
However, in this technique, each time one row is divided (i.e., each time parity bits are increased by one bit), one column with a column weight “2” is added, and hence, between the two kinds of encoding rates which are varied, both of their information sequence lengths k will be equal to each other, but their code lengths will be increased by the addition of the column.
Here, the change-over of the encoding rates has been described, but there is difficulty in the construction of the parity check matrices, as another problem of LDPC codes.
It is difficult to construct, at an arbitrary code length and an arbitrary encoding rate, a parity check matrix of which the shortest or minimum loop length in a Tanner graph is large.
Accordingly, in the past, after an LDPC code with values close to a desired code length and a desired encoding rate, respectively, has been constructed, the encoding rate has been adjusted by the use of a certain technique such as padding, puncture, etc.
Here, note that the padding is a technique in which the information sequence length k of information bits is made small by setting a part of the information bits to a certain fixed value at the time of transmission. Also, the puncture is a technique in which the length of parity bits is made small by not transmitting a part of the parity bits at the time of transmission.
However, in cases where the above-mentioned techniques have been applied, there has been a problem that a change in code length or a large deterioration in error correction capability may occur.
In addition, it is also possible to adjust the encoding rate by means of the method according to the above-mentioned first patent document, but in this case, too, the code length will be changed.
Next, reference will be made to encoding methods for LDPC codes.
There have been known some encoding methods for LDPC codes, and techniques using lower triangular matrices or staircase or step matrices have also been proposed (for example, see a first nonpatent document).
Here, an encoding using a lower triangular matrix as described in the above-mentioned first nonpatent document will be explained.
The lower triangular matrix is a matrix in which all the diagonal elements of an m×m sub-matrix which is at the rightmost side of an m×n matrix (here, m<n) are “1”, and all the elements of the rows above the diagonal elements are “0”.
In cases where the parity check matrix is a lower triangular matrix, a parity bit can be calculated based on the information bits only by carrying out exclusive OR operations.
For example, the first parity bit in a code word can be calculated by carrying out exclusive OR operations with respect to information bits corresponding to the columns which are “1” in the first row of the parity check matrix.
In addition, the j-th (>1) parity bit in the code word can be calculated by carrying out exclusive OR operations with respect to the entire information bits as well as the above-mentioned information bits and parity bits corresponding to those columns which are “1” in the j-th row of the parity check matrix, among the first through (j−1)-th parity bits. In other words, by calculating one by one in a sequential manner from the parity bit of the first bit, it is possible to calculate all the parity bits, thus making it possible to carry out an encoding.
In order to perform the above-mentioned encoding method, the parity check matrix needs to be a lower triangular matrix.
However, as described in the above-mentioned first nonpatent document, if row vectors when the rows of the parity check matrix have been transformed into vectors are linearly independent (i.e., if the rank and the number of rows of the parity check matrix match each other), the parity check matrix can be transformed into a lower triangular matrix by an elementary row operation and a column exchange (Gaussian elimination).
Here, note that the elementary row operation includes an operation which adds, to the elements of a certain row, the elements of another row in an elementwise manner (i.e., carries out exclusive OR), and a row exchange operation which exchanges two rows with each other. The column exchange is an operation which exchanges two columns with each other.
Even if the elementary row operation is carried out, a correspondence relation between the information bits of an LDPC code and a code word does not change. In other words, even if encoding is carried out based on the parity check matrix which has been transformed by the elementary row operation, the same result will be obtained as in the case where encoding is carried out based on the parity check matrix before subjected to the elementary row operation. On the other hand, when the column exchange is carried out, the correspondence relation between the information bits and the code word will collapse.
In many cases, the sparsity of “1” in the parity check matrix will be lost when an elementary row operation is carried out, so there is a technique which uses an original parity check matrix in which “1” is sparse, for decoding, and a lower triangular matrix (hereinafter referred to as an “encoding matrix”) generated as mentioned above, for encoding.
As described above, in cases where the parity check matrix is subjected to lower triangulation to generate the encoding matrix by the use of the elementary row operation and the column exchange, the correspondence relation between the parity check matrix for decoding and the encoding matrix will be collapsed by the column exchange, but in order to solve this problem, the same column exchange as that carried out in the generation process of the encoding matrix should also just be carried out with respect to the parity check matrix for decoding.